package com.sicheng.lc.杂题.前缀和之异或篇;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/13 15:24
 */
public class 每个元音包含偶数次的最长子字符串 {
    static List<Character> target = Arrays.asList('a', 'e', 'i', 'o', 'u');

    //https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/
    public int findTheLongestSubstring(String s) {
        //  将无关字符视为0 只看目标字符 做前缀和(异或和)
        //  某一段 sum[j] 期待前面出现过sum[i] 使得 sum[j]^sum[i]==0 那么(i,j]中模板字符都是偶数个
        int sum = 0;
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<>(64);
        for (int i = 0; i < s.length(); i++) {
            sum ^= target.contains(s.charAt(i)) ? s.charAt(i) : 0;
            if (sum == 0)
                max = Math.max(max, i + 1);
            else if (map.containsKey(sum)) {
                max = Math.max(max, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return max;
    }
}
